package _07_串;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/longest-string-chain/
 *
 * @Author: haogege
 * @Date: 2021/9/9
 */
public class _1048_最长字符串链 {

    public static void main(String[] args) {

        String[] strings = {"czgxmxrpx", "lgh", "bj", "cheheex", "jnzlxgh", "nzlgh", "ltxdoxc", "bju", "srxoatl", "bbadhiju", "cmpx", "xi", "ntxbzdr", "cheheevx", "bdju", "sra", "getqgxi", "geqxi", "hheex", "ltxdc", "nzlxgh", "pjnzlxgh", "e", "bbadhju", "cmxrpx", "gh", "pjnzlxghe", "oqlt", "x", "sarxoatl", "ee", "bbadju", "lxdc", "geqgxi", "oqltu", "heex", "oql", "eex", "bbdju", "ntxubzdr", "sroa", "cxmxrpx", "cmrpx", "ltxdoc", "g", "cgxmxrpx", "nlgh", "sroat", "sroatl", "fcheheevx", "gxi", "gqxi", "heheex"};

        _1048_最长字符串链 v = new _1048_最长字符串链();
        System.out.println(v.longestStrChain(strings));

    }

    // hash表实现
    public int longestStrChain(String[] words) {
        if (words.length == 1) return 1;
        int max = 0;
        HashMap<Integer, Set<String>> map = new HashMap<>();
        // 初始化hash表数据
        return max;
    }

    // 动态规划 最小时间复杂度O(n^2) 最大时间复杂度O(n^3)
    public int longestStrChain1(String[] words) {
        if (words.length == 1) return 1;

        // 先安装长度排序 O(nLogn)
        Arrays.sort(words, Comparator.comparingInt(String::length));
        int[] dp = new int[words.length];
        // O(n)
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (words[i].length() == words[j].length()) continue;
                if (words[j].length() - words[i].length() > 1) break;
                if (isPreexistent(words[i], words[j])) {
                    dp[j] = Math.max(dp[i] + 1, dp[j]);
                    max = Math.max(max, dp[j]);
                }
            }
        }
        return max;
    }


    public static boolean isPreexistent(String str1, String str2) {
        // 判断str1是否为str2的前身
        if (str1.length() != str2.length() - 1) return false;
        int index1 = 0, index2 = 0;
        int len1 = str1.length();
        int len2 = str2.length();
        while (index1 < len1 && index2 < len2) {
            if (str1.charAt(index1) == str2.charAt(index2)) index1++;
            index2++;
        }
        return index1 == len1;
    }

}
